package sort.leetcode;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @Description: 数组中的第K个最大元素
 * @Author Stark
 * @Date 2022/3/20 20:47
 **/
public class Num215_FindKthLargest {
    private static final ThreadLocalRandom random = ThreadLocalRandom.current();
    public static int findKthLargest(int[] nums, int k) {
        //方法一
        //使用库函数的快排,时间复杂度：O(nlogn)
//        Arrays.sort(nums);
//        return nums[nums.length - k];

        //方法二
        //使用优先级队列,用小堆存储,再返回堆顶
        //时间复杂度:O(nlogm)
        Queue<Integer> queue = new PriorityQueue<>(k);
        for (int i = 0; i < nums.length; i++) {
            if(i < k){
                queue.offer(nums[i]);
            }else {
                if (queue.peek() < nums[i]) {
                    queue.poll();
                    queue.offer(nums[i]);
                }
            }
        }
        return queue.poll();

        //方法三
        //使用快排的分区函数,根据索引选择区间,直到找到第k大的数
        //时间复杂度:O(n)
//        return findK(nums,0,nums.length - 1,k);
    }

//    public static int findK(int[] arr,int left,int right,int k){
//        if(left >= right){
//            return arr[left];
//        }
//        //分区函数,左区间的值都小于arr[mid]
//        //右区间的值都大于arr[mid]
//        int mid = partiton(arr,left,right);
//        //计算该值是数组中第几大的元素
//        int tmp = arr.length - mid ;
//        if(tmp < k){
//            return findK(arr,left,mid - 1,k);
//        }else if(tmp > k){
//            return findK(arr,mid + 1,right,k);
//        }else{
//            return arr[mid];
//        }
//    }
//
//    public static int partiton(int[] arr,int left,int right){
//        int randomIndex = random.nextInt(left,right);
//        swap(arr,left,randomIndex);
//        int v = arr[left];
//        int i = left + 1;
//        int j = right;
//        while(true){
//            while(i <= j && arr[i] < v){
//                i++;
//            }
//            while(i <= j && arr[j] > v){
//                j--;
//            }
//            if(i >= j){
//                break;
//            }
//            swap(arr,i,j);
//            i++;
//            j--;
//        }
//        swap(arr,left,j);
//        return j;
//    }
//
//    private static void swap(int[] arr, int left, int right) {
//        int tmp = arr[left];
//        arr[left] = arr[right];
//        arr[right] = tmp;
//    }

    public static void main(String[] args) {
        int[] arr = new int[]{3,2,3,1,2,4,5,5,6};
        System.out.println(findKthLargest(arr,4));
    }
}
